package cn.edu.xjtu.work.countPrimes;

import java.util.Arrays;

/**
 * 204. 计数质数
 * 
 * 统计所有小于非负整数 n 的质数的数量。
 */
public class Solution {
  public static void main(String[] args) {
    System.out.println(countPrimes(10));
  }

  public static int countPrimes(int n) {
    int ans = 0;
    int[] array = new int[n];
    Arrays.fill(array, 1);
    for (int i = 2; i < array.length; i++) {
      if (array[i] == 1) {
        ans++;
        int j = i + i;
        while (j < n) {
          array[j] = 0;
          j += i;
        }
      }
    }
    return ans;
  }
}
